旋转卡壳（卡尺）算法 |
您所在的位置：网站首页 › opencv 卡尺 › 旋转卡壳（卡尺）算法 |
旋转卡壳（卡尺）算法
|
申明，本文非笔者原创，原文转载自：http://hi.baidu.com/final_field/item/0c95a87c9299a65d0d0a07f0
旋转卡壳可以用于求凸包的直径、宽度，两个不相交凸包间的最大距离和最小距离等。虽然算法的思想不难理解，但是实现起来真的很容易让人“卡壳”。 拿凸包直径(也就是凸包上最远的两点的距离）为例，原始的算法是这样子： 更具体的可参见http://cgm.cs.mcgill.ca/~orm/rotcal.frame.html 
//计算凸包直径，输入凸包ch，顶点个数为n，按逆时针排列，输出直径的平方
int rotating_calipers(Point *ch,int n)
{
int q=1,ans=0;
ch[n]=ch[0];
for(int p=0;p
int x, y;
bool operator
sort(p, p+n);
ch[0]=p[0];
ch[1]=p[1];
int top=1;
for(int i=2;i
while(top>tmp&&cross(ch[top],p[i],ch[top-1])
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int rotating_calipers(Point *ch,int n)
{
int q=1,ans=0;
ch[n]=ch[0];
for(int p=0;p
//freopen("in.txt","r",stdin);
int n, len;
while(scanf("%d", &n)!=EOF)
{
for(int i = 0;i |
直接按照这个描述可以实现旋转卡壳算法，但是代码肯定相当冗长。逆向思考，如果qa，qb是凸包上最远两点，必然可以分别过qa，qb画出一对平行线。通过旋转这对平行线，我们可以让它和凸包上的一条边重合,如图中蓝色直线，可以注意到，qa是凸包上离p和qb所在直线最远的点。于是我们的思路就是枚举凸包上的所有边，对每一条边找出凸包上离该边最远的顶点，计算这个顶点到该边两个端点的距离，并记录最大的值。直观上这是一个O(n2)的算法，和直接枚举任意两个顶点一样了。但是注意到当我们逆时针枚举边的时候，最远点的变化也是逆时针的，这样就可以不用从头计算最远点，而可以紧接着上一次的最远点继续计算(详细的证明可以参见上面链接中的论文)。于是我们得到了O(n)的算法。【本文地址】